#include <bits/stdc++.h>

using namespace std;

class Node {
public:
    vector<int> fa;
    Node(int n){
        fa.resize(n);
        for(int i = 0; i < n; i++) fa[i]=i;
    }
    int find(int x){
        if(fa[x] != x) fa[x] = find(fa[x]);
        return fa[x];
    }
    void work(int x, int y){
        int xx = find(x);
        int yy = find(y);
        if(xx != yy) fa[yy] = xx;
    }
};

class Solution {
public:
    int countComponents(vector<int>& nums, int threshold) {
        vector<int> v;
        int a = 0;
        for(auto &t : nums){
            if(t <= threshold) v.push_back(t);
            else a++;
        }
        int n = v.size();
        if(n == 0) return a;
        vector<int> vis(threshold + 1, -1);
        for(int i = 0;i < n; i++) vis[v[i]] = i;
        Node no(n);
        for(int i = 1; i <= threshold; i++){
            vector<int> tem;
            int c = sqrt(i);
            for(int j = 1; j <= c; j++){
                if(i % j == 0){
                    if(vis[j] != -1) tem.push_back(vis[j]);
                    int k = i / j;
                    if(k != j && k <= threshold && vis[k] != -1) tem.push_back(vis[k]);
                    // printf("%d\n", k);
                }
            }
            if(tem.size() >= 2){
                int first = tem[0];
                for(int i=1;i<tem.size();i++) no.work(first, tem[i]);
            }
        }
        unordered_set<int> pa;
        for(int i = 0; i < n; i++) pa.insert(no.find(i));
        return pa.size() + a;
    }
};